// Gabriel Tessaroli   - 4321450
// Lucas Nunes Arvani  - 7986802
// Lucas Fúrio Franco  - 6793010

#include <queue>
#include <stdio.h>
#include <cstdlib>
#include <string.h>

// criado para auxiliar a inserção no struct
#define assign(a,b,c) a.vertice = b; a.distance = c

using namespace std;

// criado para fazer a relação de duas vértices e sua distancia
typedef struct {

	int vertice;
	int distance;

} neighbor;

// classe usada para setar a posicao do
// novo valor a ser inserido fila de prioridade
class compare{
private:
	int *dist;
public:
	compare(int *a) { this->dist = a; }

	bool operator() (const int& a, const int& b) {
		return dist[a] > dist[b];
	}
};


int main(int argc, char *argv[]) {

	// numero de vertices, e numero de ligaçoes
	int n_vertices, n_edges;

	//'x' e 'y' são auxiliares que representam os cruzamentos
	//'dist' é a distancia entre os pontos x e y
	int x, y, dist;
	// auxiliares para interações
	int i, j;

	// distance - vetor usado para saber a distancia total de um ponto até outro (usado no algoritmo)
	// visit - vetor usado para saber a quais vértices ja foram percorridos no algoritmo
	int *distance, *visit;

	neighbor n, _n;

	// vetor usado para setar a maior distancia entre a origem e um vértice
	int *max;

	// inicializa grafo (uma matriz)
	vector<vector < neighbor > > graph;

	// pega numero de cruzamentos e de ruas
	scanf("%d %d", &n_vertices,  &n_edges);

	// cria o primeiro vetor de cidades
	for(i=0; i<n_vertices; ++i) {
		graph.insert(graph.end(), vector<neighbor >());
	}

	// monta o grafo, marcando as ligações entre os cruzamentos e suas distancias
	for(i=0; i<n_edges; ++i) {
		// pega os dois cruzamentos e a distancia entre eles
		scanf("%d %d %d", &x, &y, &dist);
		// decrementa x e y, pois vetor começa do 0
		x--; y--;

		// n.vertice = y
		// n.dist = dist
		// n é auxiliar.
		assign (n, y, dist);

		// entra na posição do cruzamento 'x' e insere 'n' (sua relação com o cruzamento 'y')
		graph.at(x).insert(graph.at(x).end(), n);

		// entra na posição do cruzamento 'y' e insere 'n' (sua relação com o cruzamento 'x')
		n.vertice = x;
		graph.at(y).insert(graph.at(y).end(), n);
	}

	// Inicializa vetores de inteiros para calculo de dijkstra
	distance = (int *) malloc(sizeof(int) * n_vertices);
	visit = (int *) malloc(sizeof(int) * n_vertices);
	max = (int *) malloc(sizeof(int) * n_vertices);

	// Realiza o Dijkstra adotando cada vértice como origem.
	for(i=0; i<n_vertices; ++i) {

		// Inicializa a fila de prioridade
		priority_queue<int, vector<int>, compare> neighborhood (distance);

		// Seta valores iniciais para a realização do Dijkstra
		for(j=0; j<n_vertices; ++j) {
			distance[j] = -1;
			visit[j] = 0;
		}

		// Atribui um ponto inicial, que é a distancia do vértice
		// até ele mesmo, ou seja, a distancia será de zero.
		assign(n, i, 0);

		// insere na fila o primeiro valor.
		neighborhood.push(i);

		// atribui na tabela de distancia, o valor até ele mesmo
		// que será zero. E marca como visitado a vértice
		distance[i] = 0; visit[i] = 1;

		// _max será a distancia do caminho encontrado da
		// vértice de origem até uma a vértce mais distante.
		int _max = 0;

		// Enquanto tiver alguma vértice na fila ele realiza o algoritmo
		while(!neighborhood.empty()) {

			// pega o vértice com maior prioridade
			n.vertice = neighborhood.top();
			n.distance = distance[n.vertice];

			// retira vértice da fila
			neighborhood.pop();

			// marca vértice como visitado
			visit[n.vertice] = 1;
			// verefica se é o maior caminho
			if (n.distance > _max) _max = n.distance;

			// verefica todos os caminhos conectados com o vértice
			for(j=0; j<graph.at(n.vertice).size(); ++j) {

				// _n recebe um vértice ligado ao vértice 'n'
				_n = graph.at(n.vertice).at(j);

				// seta nova distancia caso ela seja menor que o atual
				if ((!visit[_n.vertice]) &&
					(distance[_n.vertice] == -1 || distance[_n.vertice] > (_n.distance + n.distance)) ) {
					_n.distance = _n.distance + n.distance;
					distance[_n.vertice] = _n.distance;
					neighborhood.push(_n.vertice);
				}

			}

		}

		// coloca na posição do vértice de origem a maior distancia encontrada.
		max[i] = _max;

	}


	// verefica todos os maiores caminhos de cada vértice origem
	// e pega o vértice com o menor dentre eles. Este será o de melhor localidade.
	int min = max[0];
	for(i=0; i<n_vertices; ++i)
		if (min > max[i])
			min = max[i];


	printf("%d\n", min);

	// libera memória
	free(distance);
	free(visit);
	free(max);

	return 0;
}
